#include "bst.h"

bst *bstHead = NULL;

char *files[20];
int inc = 0;

void nullHead(){
bstHead = NULL;
}

void add_elt(char *flpath)
{
	bst *prev,*travel;
	char data[500];
	strcpy(data,flpath);
	
	travel = (bst*)malloc(sizeof(bst));

	bst *temp=(bst*)malloc(sizeof(bst));	
	strcpy(temp->fullpath,data);
	temp->parent = NULL;
	temp->lchild = NULL;
	temp->rchild = NULL; 
	
	if(bstHead == NULL)
	  bstHead = temp;
	else
	{
	
		travel =  bstHead;
		prev = bstHead;
		while(travel != NULL)
		{
			
		   	prev = travel;
			
			if(strcmp(temp->fullpath,travel->fullpath)<0)
			{
				 travel = travel -> lchild;
			}			 
			else
			 {
				 travel = travel->rchild;			
			 }
		}
		
		temp->parent = prev;
				
		if(strcmp(temp->fullpath,prev->fullpath)<0)
		{
			prev->lchild = temp;
		}
		else
		{
			
			prev->rchild = temp;
		}
		   
	}
	//printf("Element inserted successfully\n");
	//free(temp);
}

bst* gethead(){

return bstHead;
}

void display(bst *disp)
{
   if(disp != NULL)
    {
	display(disp->lchild);
	//printf("%s\n",disp->fullpath);
	display(disp->rchild);
     }
}

/*
long search_elt(char *filepath)
{
    bst* node = bstHead;
while(node != NULL && (strcmp(filepath,node->fullpath) != 0))
{
  if(strcmp(filepath,node->fullpath)< 0)
      node = node->lchild;
  else
      node = node->rchild;
}

return node->blockno;
}
*/

//traverse

int search_file(char *str,bst *start){
	printf("\b");    
	int flag = 1;
    char *p,*q;
    char filepath[50];
	//printf(" ");
	int count = 0;
    if(start != NULL){
	if(start->lchild != NULL)
        	search_file(str,start->lchild);
	strcpy(filepath,start->fullpath);
        p = returnfileName(filepath);
	//printf("Filename is %s\n",p);
	q = str;
	while(*p && *q)
	{
		if(*p != *q)
		flag = 0;
		p++;
		q++;
	}
        if(flag == 1){
            count++;
            inc++;
        }
	if(start->rchild != NULL)
        	search_file(str,start->rchild);
    }
	if(count > 0)
		return 1;
	else 
		return 0;
    //return files;
}

char* returnfileName(char *path)
{
char *a;
char *token;
token = strtok(path,"/");
while (token != NULL) {
    	a = token;
    token = strtok(NULL, "/");
}
return a;
}


bst* minimum()
{
bst *first = bstHead;
while(first->lchild != NULL)
first = first->lchild;
return first;
}

bst* search_delete(char* flpath)
{
    bst *pass = bstHead;
while(pass != NULL && (strcmp(flpath,pass->fullpath)!=0))
{
  if(strcmp(flpath,pass->fullpath)<0)
	pass = pass->lchild;
  else
	pass = pass->rchild;
}

return pass;

}

void transplant(bst *out,bst *in)
{
 if(out->parent == NULL)
   bstHead = in;
 else if(out == out->parent->lchild)
   out->parent->lchild = in;
 else
   out->parent->rchild =  in;
if(in != NULL)
in->parent = out->parent;
}


int delete_node(char *path)
{
int k;
bst *elt,*min;
elt=search_delete(path);
if(elt != NULL)
{
  if(elt->lchild == NULL)
	transplant(elt,elt->rchild);
  else if(elt->rchild == NULL)
	transplant(elt,elt->lchild);
  else{
	min = minimum();
	if(min->parent != elt)
	{
	  transplant(min,min->rchild);
	  min->rchild = elt->rchild;
	  min->rchild->parent = min;
	}
	transplant(elt,min);
	min->lchild = elt->lchild;
	min->lchild->parent = min;
	
       }
}
else
{
//printf("Element does not exists so cannot be deleted");
return 0;
}
return 1;
}


